{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Check if There is a Path With Equal Number of 0's And 1's"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isThereAPath"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #检查是否有路径经过相同数量的 0 和 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个 <strong>下标从 0 开始</strong> 的 <code>m x n</code> 的 <strong>二进制</strong> 矩阵 <code>grid</code> ，从坐标为 <code>(row, col)</code> 的元素可以向右走 <code>(row, col+1)</code> 或向下走 <code>(row+1, col)</code> 。</p>\n",
    "\n",
    "<p>返回一个布尔值，表示从 <code>(0, 0)</code> 出发是否存在一条路径，经过 <strong>相同</strong> 数量的 <code>0</code> 和 <code>1</code>，到达终点 <code>(m-1, n-1)</code> 。如果存在这样的路径返回 <code>true</code> ，否则返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1 ：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/12/20/yetgriddrawio-4.png\" />\n",
    "<pre>\n",
    "<b>输入：</b>grid = [[0,1,0,0],[0,1,0,0],[1,0,1,0]]\n",
    "<b>输出：</b>true\n",
    "<b>解释：</b>以上图中用蓝色标记的路径是一个有效的路径，因为路径上有 3 个值为 1 的单元格和 3 个值为 0 的单元格。由于存在一个有效的路径，因此返回 true 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2 ：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/12/20/yetgrid2drawio-1.png\" style=\"width: 151px; height: 151px;\" />\n",
    "<pre>\n",
    "<b>输入：</b>grid = [[1,1,0],[0,0,1],[1,0,0]]\n",
    "<b>输出：</b>false\n",
    "<b>解释：</b>这个网格中没有一条路径经过相等数量的0和1。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>2 &lt;= m, n &lt;= 100</code></li>\n",
    "\t<li><code>grid[i][j]</code> 不是&nbsp;<code>0</code> 就是&nbsp;<code>1</code> 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [check-if-there-is-a-path-with-equal-number-of-0s-and-1s](https://leetcode.cn/problems/check-if-there-is-a-path-with-equal-number-of-0s-and-1s/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [check-if-there-is-a-path-with-equal-number-of-0s-and-1s](https://leetcode.cn/problems/check-if-there-is-a-path-with-equal-number-of-0s-and-1s/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,1,0,0],[0,1,0,0],[1,0,1,0]]', '[[1,1,0],[0,0,1],[1,0,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isThereAPath(self, grid: List[List[int]]) -> bool:\n",
    "        m, n, nhas, x = len(grid), len(grid[0]), [1] + [0] * (len(grid[0])-1), 1\n",
    "        if (m+n) % 2 == 0: return False\n",
    "        for lis in grid:\n",
    "            has, nhas = nhas, [nhas[0] << lis[0]]\n",
    "            for i in range(1,n): nhas.append((nhas[-1]|has[i]) << lis[i])\n",
    "        return 1 << ((m+n)//2) & nhas[-1] > 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isThereAPath(self, grid: List[List[int]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if (m + n - 1) & 1: return False\n",
    "        # [1] 为初始值，表示当前初始位置有一条 0 个 1 的路径\n",
    "        cur = [1] + [0] * (n - 1)\n",
    "        for line in grid:\n",
    "            pre, cur = cur, [cur[0] << line[0]]\n",
    "            for i in range(1, n):\n",
    "                cur.append((cur[-1] | pre[i]) << line[i])\n",
    "        return bool(cur[-1] >> ((m + n) >> 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def isThereAPath(self, grid: List[List[int]]) -> bool:\n",
    "        m, n, nhas, x = len(grid), len(grid[0]), [1] + [0] * (len(grid[0])-1), 1\n",
    "        if (m+n) % 2 == 0:\n",
    "            return False\n",
    "        for lis in grid:\n",
    "            has, nhas = nhas, [nhas[0] << lis[0]]\n",
    "            for i in range(1, n):\n",
    "                nhas.append((nhas[-1] | has[i]) << lis[i])\n",
    "        return 1 << ((m+n)//2) & nhas[-1] > 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isThereAPath(self, grid: List[List[int]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if (m + n - 1) % 2:\n",
    "            return False\n",
    "        \n",
    "        if grid[0][0]:\n",
    "            dp = [[1, 1]]\n",
    "        else:\n",
    "            dp = [[-1, -1]]\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            if grid[0][i]:\n",
    "                flag = 1\n",
    "            else:\n",
    "                flag = -1\n",
    "            dp.append([dp[-1][0] + flag, dp[-1][1] + flag])\n",
    "        \n",
    "        for i in range(1, m):\n",
    "            if grid[i][0]:\n",
    "                flag = 1\n",
    "            else:\n",
    "                flag = -1\n",
    "            dp[0][0] += flag\n",
    "            dp[0][1] += flag\n",
    "            for j in range(1, n):\n",
    "                if grid[i][j]:\n",
    "                    flag = 1\n",
    "                else:\n",
    "                    flag = -1\n",
    "                dp[j] = [min(dp[j][0], dp[j-1][0]) + flag, max(dp[j][1], dp[j-1][1]) + flag]\n",
    "        \n",
    "        return dp[-1][0] <= 0 <= dp[-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isThereAPath(self, grid: List[List[int]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if (m + n - 1) % 2:\n",
    "            return False\n",
    "        \n",
    "        if grid[0][0]:\n",
    "            dp = [[1, 1]]\n",
    "        else:\n",
    "            dp = [[-1, -1]]\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            if grid[0][i]:\n",
    "                flag = 1\n",
    "            else:\n",
    "                flag = -1\n",
    "            dp.append([dp[-1][0] + flag, dp[-1][1] + flag])\n",
    "        \n",
    "        for i in range(1, m):\n",
    "            if grid[i][0]:\n",
    "                flag = 1\n",
    "            else:\n",
    "                flag = -1\n",
    "            dp[0][0] += flag\n",
    "            dp[0][1] += flag\n",
    "            for j in range(1, n):\n",
    "                if grid[i][j]:\n",
    "                    flag = 1\n",
    "                else:\n",
    "                    flag = -1\n",
    "                dp[j] = [min(dp[j][0], dp[j-1][0]) + flag, max(dp[j][1], dp[j-1][1]) + flag]\n",
    "        \n",
    "        return dp[-1][0] <= 0 <= dp[-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isThereAPath(self, grid: List[List[int]]) -> bool:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        if (m + n) % 2 == 0:\n",
    "            return False\n",
    "\n",
    "        max_ones = [[0] * n for _ in range(m)]\n",
    "        min_ones = [[0] * n for _ in range(m)]\n",
    "        max_ones[-1][-1] = min_ones[-1][-1] = grid[-1][-1]\n",
    "\n",
    "        # last row\n",
    "        for j in range(n - 2, -1, -1):\n",
    "            min_ones[-1][j] = max_ones[-1][j] = max_ones[-1][j + 1] + grid[-1][j]\n",
    "        \n",
    "        # last col\n",
    "        for i in range(m - 2, -1, -1):\n",
    "            min_ones[i][-1] = max_ones[i][-1] = max_ones[i + 1][-1] + grid[i][-1]\n",
    "\n",
    "        for i in range(m - 2, -1, -1):\n",
    "            for j in range(n - 2, -1, -1):\n",
    "                max_ones[i][j] = max(max_ones[i + 1][j], max_ones[i][j + 1]) + grid[i][j]\n",
    "                min_ones[i][j] = min(min_ones[i + 1][j], min_ones[i][j + 1]) + grid[i][j]\n",
    "\n",
    "        return min_ones[0][0] <= (m + n) // 2 <= max_ones[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isThereAPath(self, grid: List[List[int]]) -> bool:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        if (m + n) % 2 == 0:\n",
    "            return False\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        dp[0][0] = 1 << (m + n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i > 0:\n",
    "                    dp[i][j] |= dp[i - 1][j]\n",
    "                if j > 0:\n",
    "                    dp[i][j] |= dp[i][j - 1]\n",
    "                if grid[i][j] == 1:\n",
    "                    dp[i][j] <<= 1\n",
    "                else:\n",
    "                    dp[i][j] >>= 1\n",
    "        return bool(dp[-1][-1] & 1 << (m + n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def isThereAPath(self, grid: List[List[int]]) -> bool:\r\n",
    "        m, n = len(grid), len(grid[0])\r\n",
    "        if (m + n) % 2 == 0:\r\n",
    "            return False\r\n",
    "        f = [[0] * n for _ in range(m)]\r\n",
    "        f[0][0] = 1 << m + n\r\n",
    "        for i in range(m):\r\n",
    "            for j in range(n):\r\n",
    "                if i > 0:\r\n",
    "                    f[i][j] |= f[i - 1][j]\r\n",
    "                if j > 0:\r\n",
    "                    f[i][j] |= f[i][j - 1]\r\n",
    "                if grid[i][j] == 1:\r\n",
    "                    f[i][j] <<= 1\r\n",
    "                else:\r\n",
    "                    f[i][j] >>= 1\r\n",
    "        return bool(f[-1][-1] & 1 << m + n)\r\n",
    "        \r\n",
    "\r\n",
    "    def isThereAPath2(self, grid: List[List[int]]) -> bool:\r\n",
    "        m,n = len(grid),len(grid[0])\r\n",
    "        # 目标为 m+n-1个格子， 如果它本身都不是偶数，直接返回false\r\n",
    "        if (m+n-1)%2 != 0:\r\n",
    "            return False \r\n",
    "        # 只能往右边或者下边走\r\n",
    "        # dp[i][j][k]表示到i,j格的时候，累计的1有k个\r\n",
    "        # i,j本身是1\r\n",
    "        # dp[i][j][k] = dp[i][j-1][k-1]|dp[i-1][j][k-1]\r\n",
    "        # i,j本身不是1\r\n",
    "        # dp[i][j][k] = dp[i][j-1][k]|dp[i-1][j][k]\r\n",
    "        dp = [[[False for k in range(m+n+1)] for j in range(n+1)] for i in range(m+1)]\r\n",
    "        # base: dp[0][1][0] = True \r\n",
    "        dp[0][1][0] = True \r\n",
    "        for i in range(1,m+1):\r\n",
    "            for j in range(1,n+1):\r\n",
    "                for k in range(i+j+1): # 这里可以优化成i+j+1\r\n",
    "                    if grid[i-1][j-1] == 1:\r\n",
    "                        dp[i][j][k] = dp[i][j-1][k-1]|dp[i-1][j][k-1]\r\n",
    "                    else:\r\n",
    "                        dp[i][j][k] = dp[i][j-1][k]|dp[i-1][j][k]\r\n",
    "        return dp[m][n][(m+n-1)//2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isThereAPath(self, grid: List[List[int]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if (m + n) % 2 == 0:\n",
    "            return False \n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, j, diff):\n",
    "            if m + n - 2 - i - j < abs(diff):\n",
    "                return False \n",
    "            if i == m - 1 and j == n - 1:\n",
    "                return diff == 0\n",
    "            if i == m - 1:\n",
    "                return dfs(i, j + 1, diff + 2 * grid[i][j + 1] - 1)\n",
    "            if j == n - 1:\n",
    "                return dfs(i + 1, j, diff + 2 * grid[i + 1][j] - 1)\n",
    "            return dfs(i, j + 1, diff + 2 * grid[i][j + 1] - 1) or dfs(i + 1, j, diff + 2 * grid[i + 1][j] - 1)\n",
    "\n",
    "        ans = dfs(0, 0, 2 * grid[0][0] - 1)\n",
    "        dfs.cache_clear()\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isThereAPath(self, grid: List[List[int]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if (m + n) % 2 == 0:\n",
    "            return False \n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, j, diff):\n",
    "            # if m + n - 2 - i - j < abs(diff):\n",
    "            #     return False \n",
    "            if i == m - 1 and j == n - 1:\n",
    "                return diff == 0\n",
    "            if i == m - 1:\n",
    "                return dfs(i, j + 1, diff + 2 * grid[i][j + 1] - 1)\n",
    "            if j == n - 1:\n",
    "                return dfs(i + 1, j, diff + 2 * grid[i + 1][j] - 1)\n",
    "            return dfs(i, j + 1, diff + 2 * grid[i][j + 1] - 1) or dfs(i + 1, j, diff + 2 * grid[i + 1][j] - 1)\n",
    "\n",
    "        ans = dfs(0, 0, 2 * grid[0][0] - 1)\n",
    "        dfs.cache_clear()\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isThereAPath(self, grid: List[List[int]]) -> bool:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        # 目标为 m+n-1个格子， 如果它本身都不是偶数，直接返回false\n",
    "        if (m+n-1)%2 != 0:\n",
    "            return False \n",
    "\n",
    "        # 只能往右边或者下边走\n",
    "        # dp[i][j][k]表示到i,j格的时候，累计的1有k个\n",
    "        # i,j本身是1\n",
    "        # dp[i][j][k] = dp[i][j-1][k-1]|dp[i-1][j][k-1]\n",
    "        # i,j本身不是1\n",
    "        # dp[i][j][k] = dp[i][j-1][k]|dp[i-1][j][k]\n",
    "        dp = [[[False for k in range(m+n+1)] for j in range(n+1)] for i in range(m+1)]\n",
    "        # base: dp[0][1][0] = True \n",
    "        dp[0][1][0] = True \n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                for k in range(i+j+1): # 这里可以优化成i+j+1\n",
    "                    if grid[i-1][j-1] == 1:\n",
    "                        dp[i][j][k] = dp[i][j-1][k-1]|dp[i-1][j][k-1]\n",
    "                    else:\n",
    "                        dp[i][j][k] = dp[i][j-1][k]|dp[i-1][j][k]\n",
    "\n",
    "        return dp[m][n][(m+n-1)//2]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # dp\n",
    "    # 在lc上，有往右往下的规则限制的情况下就去考虑DP 如果四个方向都有，大概率是图的搜索 这里可以用一些trick来提升搜索效率 注意base的设置\n",
    "    def isThereAPath(self, grid: List[List[int]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        # 目标为 m+n-1个格子， 如果它本身都不是偶数，直接返回false\n",
    "        if (m+n-1) % 2 != 0:\n",
    "            return False \n",
    "\n",
    "        # 只能往右边或者下边走\n",
    "        # dp[i][j][k]表示到i,j格的时候，累计的1有k个\n",
    "        # i,j本身是1\n",
    "        # dp[i][j][k] = dp[i][j-1][k-1] | dp[i-1][j][k-1]\n",
    "        # i,j本身不是1\n",
    "        # dp[i][j][k] = dp[i][j-1][k] | dp[i-1][j][k]\n",
    "        dp = [[[False for k in range(m+n+1)] for j in range(n+1)] for i in range(m+1)]\n",
    "        # base: dp[0][1][0] = True \n",
    "        dp[0][1][0] = True\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                for k in range(i+j+1): # 这里可以优化成i+j+1\n",
    "                    if grid[i-1][j-1] == 1:\n",
    "                        dp[i][j][k] = dp[i][j-1][k-1] | dp[i-1][j][k-1]\n",
    "                    else:\n",
    "                        dp[i][j][k] = dp[i][j-1][k] | dp[i-1][j][k]\n",
    "\n",
    "        return dp[m][n][(m+n-1) // 2]\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
